The present invention is related to pulse or digital communications. In particular, the present invention is related to rate synchronization or adaptation associated with data transmission in private or public networks using bit insertion or stuffing.
In modern date communications, when data are transmitted through a data channel or “bit pipe”, data are typically structured into frames. Framing serves not only to separate data from control information or channel overhead, but allows one user data rate to be adapted, for example, to a higher data rate or bit rate provided by an underlying protocol layer associated with, for example, the data channel or bit pipe. In accordance with typical framing schemes, frame start positions must be identified for synchronization purposes and to allow receivers access to known positions within the frame where payload data is located. In order to identify frame boundaries, frames must either have a uniquely identifiable frame header or frame separator typically embodied in, for example, a unique bit pattern. However, due to the random nature of data contained in, for example, the payload portion of the frame, random occurrences of the frame start identifier bit pattern are possible. To assure uniqueness, the bit pattern associated with the frame start identifier must not be allowed to occur within the data associated with the remainder of the frame contents. Thus, to ensure, for example, data transparency and to ensure proper frame synchronization, random occurrences of the frame start identifier bit pattern must be removed from the data payload portion and any non-frame identifier portion of the frame contents.
As a practical example, it will be appreciated by those skilled in the art that in accordance with, for example, ITU-T V.110, the start of a frame is identified by a zero octet which consists of 8 consecutive zero bits. In such a scheme, data transparency is ensured by ensuring that each following octet in the V.110 frame starts with a 1 bit. Data transparency overhead in such a scheme is referred to as 1/7, meaning one extra bit for every seventh data bit.
In accordance with other schemes, flag stuffing may be used to achieve data transparency. One common scheme within the HDLC protocol is often referred to as X.31 flag stuffing. In accordance with X.31 flag stuffing, HDLC frames are separated by flags consisting of the following eight bits: 01111110. It can be seen that the flag therefore consists of a zero bit followed by six 1 bits. When flag stuffing is applied on a synchronous bit stream, data transparency is ensured by bit stuffing, which consists of inserting an extra 0 bit after each sequence of five consecutive 1 bits of data at the sender and removing each 0 bit occurring after five consecutive 1 bits of data at the receiver. Otherwise, random occurrences of six consecutive 1 bits of data would be confused by a receiver as a flag signaling the beginning of a new frame. Thus, the worst case data transparency overhead in such a scheme is 1/5, e.g. one extra 0 bit inserted for every fifth bit. It should be noted however that the worst case scenario occurs only when a frame contains a data payload consisting entirely of 1 bits and that, on average, the data transparency overhead is much less.
A typical flag stuffing rate adaptation scheme 100 is illustrated in FIG. 1. At sender 110, flags may be inserted in flag stuffing block 113 between frame in 111 and subsequent frame in 111, after ensuring, in bit stuffing block 112, that there are no accidental occurrences of flags within frame data. In FIG. 2, a typical bit stuffing scheme 200 is illustrated. As can be seen, a zero bit may be added after each sequence of five ones in the frame. Frame 210 may represent raw frame data being processed, for example, by a sender such as sender 110. Data segment 211 contains five consecutive 1 bits, therefore in processed frame 220, zero bit 221 appears after data segment 211. It should be noted that to reduce processing overhead, frame 210 is preferably processed bitwise. Accordingly, it is not known by, for example, a bit stuffing block such as bit stuffing block 112, whether the next bit will be a one or a zero. Since data segment 211 only contains five consecutive ones, it would not be interpreted as a flag. In accordance with typical bit stuffing protocols, however, zero bit 221 will be inserted anyway. Data segment 212 contains six consecutive 1 bits and could be interpreted as a flag by a receiver. Thus, zero bit 222 is inserted after the fifth consecutive 1 bit of data segment 212 as shown. By bit stuffing in the above described manner, it is virtually guaranteed that a flag will not appear in processed frame 220.
Problems arise however, in that schemes for identifying embedded frame start identifier bit patters and ensuring data transparency add overhead. It is a competing desire in the art to reduce overhead as much as possible in order to maximize utilization of available bandwidth. Accordingly, in still other bit stuffing schemes such as that provided for in GSM TS 08.20, A-TRAU overhead may be reduced since frames are defined with a data transparency scheme having an overhead of 1/36. It should be noted that the scheme is fairly complicated, and interested readers are referred to TS 08.20 for further details. In other cases it may further be possible to perform flag stuffing in conjunction with V.110, A-TRAU.
U.S. Pat. No. 5,835,602 to Lang describes an approach wherein packet based mappings may be scrambled before insertion into, for example, a payload envelope. The purpose of such a scheme includes avoiding the possibility of generating arbitrarily long run lengths of a transmitted sequence thus disrupting a system. Lang does not disclose schemes associated with rate adaptation and cannot reduce and predict more accurately rate adaptation overhead and thus assure high levels of transmission efficiency. Moreover, Lang describes scrambling flag sequences which would be antithetical to rate adaptation schemes. Differences between Lang and rate adaptation schemes may be better appreciated as Lang describes how scrambling is used to aid clock recovery
Problems arise however with known rate adaptation solutions. For example, the V.110 rate adaptation protocol is designed only for certain specific rates. Although the V.110 principle, namely to use a zero octet to identify the start of a frame and let each subsequent octet begin with a 1, may be used in a more general manner it may not be easy to apply. For example, V.110 also uses TDMA frames associated with, for example, ISDN compliant networks to adapt to rates up to 56 kbit/s to 64 kbit/s, but this special case is difficult to generalize. It should further be noted that V.110 has a fairly high overhead. A-TRAU is also designed for specific rates, and while its principles may also be applied generally, and overhead is fairly low, e.g. 17 bits at frame start, and one bit in 36 bits for data transparency, the A-TRAU rate adaptation scheme is rather complicated and requires more processing than V.110 and flag stuffing. It should be noted that, while overhead is constant for V.110 and A-TRAU, overhead becomes variable in the case of flag stuffing since the number of bits needed depends of frame contents. The implication of content dependent, variable overhead implies that throughput may also be variable. Accordingly, flag stuffing is used typically in combination with flow control at a higher protocol layer. In order to avoid flow control, it becomes necessary to budget sufficient bandwidth on the underlying layer such that the maximum resulting bit rate including frames, stuffed bits and flags never exceeds the budgeted bandwidth.
FIG. 3 illustrates communication scenario 300 wherein different transfer technologies may be used on two adjoining links 301 and 302. Asynchronous transfer mode (ATM) may be used on link 301 between Node A 310 and Node B 320, and a 64 kbit/s synchronous link 302 may be used between Node B 320 and Node C 330. Frames 311 sent from Node A 310 to Node B 320 may be relayed to Node C 330 using flags and stuffing bits 321 between Node B 320 and Node C 330. It should be noted that there is preferably no flow control between Node A 310 and Node B 320, hence the bit rate between Node A 310 and Node B 320 must preferably be limited sufficiently so that when flags and stuffing bits 321 are added, the resulting bit rate will never exceed 64 kbit/s. Otherwise, frames 311 will be dropped at Node B 320.
It should further be noted that data transparency overhead, e.g., the number of bits that need to be stuffed in the frames, is dependent on higher layer TI protocol 303 and the nature of user data that are transmitted thereover. Often, higher layer protocol 303 may use fixed sized Packet Data Units (PDU). In situations where there are not sufficient data to completely fill a fixed size PDU, 1 bits may be inserted as fill. Problems arise however, in that filling incomplete PDUs with 1 bits may create long sequences of ones in frames 311 and a correspondingly large number of stuffed zeroes due to bit stuffing. Also, the nature of the user data may be such that a large number of zeroes may further need to be stuffed on the basis of the user data. Budgeting for the worst case would include a data transparency overhead equal to 1/5. In such a situation, alternate protocols, such as, for example, V.110, are better suited. Consider an example where the data rate is 57.6 kbit/s and data are structured into frames 576 bits long and transmitted every 10 ms. In a worst case scenario using fixed size PDUs, 115 bits of overhead would be needed to ensure data transparency. In addition, at least one flag needs to be transmitted between every frame. In order to guarantee a constant throughput of 57.6 kbit/s, the data channel or bit pipe must allow 576+115+8 bits to be transmitted in 10 ms yielding a bit rate of 69.9 kbit/s. In such a scenario, 64 kbit/s link 302 will not suffice for guaranteeing a throughput of 57.6 kbit/s if flag stuffing is used. An alternate protocol should preferably be used. It should be noted however, that although V.110 would not be applicable to such a case, A-TRAU protocol would be better suited for such an application.
Thus a method and apparatus for allowing rate adaptation to be performed while not exceeding available bandwidth would be appreciated in the art.